package com.sheng.leetcode.year2025.month09.day16;

import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2025/9/26
 * <p>
 * 2197. 替换数组中的非互质数<p>
 * <p>
 * 给你一个整数数组 nums 。请你对数组执行下述操作：<p>
 * 从 nums 中找出 任意 两个 相邻 的 非互质 数。<p>
 * 如果不存在这样的数，终止 这一过程。<p>
 * 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。<p>
 * 只要还能找出两个相邻的非互质数就继续 重复 这一过程。<p>
 * 返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。<p>
 * 生成的测试用例可以保证最终数组中的值 小于或者等于 108 。<p>
 * 两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。<p>
 * <p>
 * 示例 1 ：<p>
 * 输入：nums = [6,4,3,2,7,6,2]<p>
 * 输出：[12,7,6]<p>
 * 解释：<p>
 * - (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。<p>
 * - (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。<p>
 * - (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。<p>
 * - (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。<p>
 * 现在，nums 中不存在相邻的非互质数。<p>
 * 因此，修改后得到的最终数组是 [12,7,6] 。<p>
 * 注意，存在其他方法可以获得相同的最终数组。<p>
 * <p>
 * 示例 2 ：<p>
 * 输入：nums = [2,2,1,1,3,3,3]<p>
 * 输出：[2,1,1,3]<p>
 * 解释：<p>
 * - (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。<p>
 * - (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。<p>
 * - (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。<p>
 * 现在，nums 中不存在相邻的非互质数。<p>
 * 因此，修改后得到的最终数组是 [2,1,1,3] 。<p>
 * 注意，存在其他方法可以获得相同的最终数组。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 1 <= nums[i] <= 10^5<p>
 * 生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。<p>
 */
public class LeetCode2197 {

    @Test
    public void test() {
//        int[] nums = {6, 4, 3, 2, 7, 6, 2};
//        int[] nums = {2, 2, 1, 1, 3, 3, 3};
//        int[] nums = {31, 97561, 97561, 97561, 97561, 97561, 97561, 97561, 97561};
        int[] nums = {11, 9, 3, 9, 3, 9, 33};
        System.out.println(new Solution().replaceNonCoprimes(nums));
    }
}

class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        // 获取两个数的最大公约数，和最小公倍数
        Deque<Integer> stack = new LinkedList<>();
        for (int num : nums) {
            stack.push(num);
            // 检查栈顶两个元素是否需要合并
            while (stack.size() >= 2) {
                int a = stack.pop();
                int b = stack.pop();
                int gcdValue = gcd(a, b);
                if (gcdValue > 1) {
                    // 计算 LCM 并合并
                    int lcm = (int) ((long) a / gcdValue * b);
                    stack.push(lcm);
                } else {
                    // 不需要合并，恢复栈状态
                    stack.push(b);
                    stack.push(a);
                    break;
                }
            }
        }
        // 将栈转换为列表（顺序需要反转）
        List<Integer> result = new ArrayList<>(stack);
        Collections.reverse(result);
        return result;
        // 使用 list 超时
//        List<Integer> list = new LinkedList<>();
//        for (int num : nums) {
//            list.add(num);
//        }
//        int i = 0;
//        while (i < list.size() - 1) {
//            if (gcd(list.get(i), list.get(i + 1)) > 1) {
//                int lcm = lcm(list.get(i), list.get(i + 1));
//                list.set(i, lcm);
//                list.remove(i + 1);
//                if (i > 0) {
//                    i--;
//                }
//            } else {
//                i++;
//            }
//        }
//        return list;
    }

    /**
     * 最大公约数
     *
     * @param a
     * @param b
     * @return 两个数的最大公约数
     */
    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    /**
     * 最小公倍数
     *
     * @param a
     * @param b
     * @return 两个数的最小公倍数
     */
    public int lcm(int a, int b) {
        // 使用 long 避免溢出
        long product = (long) a * b;
        return (int) (Math.abs(product) / gcd(a, b));
    }
}
